# 二叉树的前序、中序、后序遍历
class Node:

    def __init__(self, val: str):
        self.val = val
        self.left = None
        self.right = None


res = []


def back_trace(n: Node):
    global res
    # 前序
    res.append(n.val)
    if n.left is not None:
        back_trace(n.left)
    # 中序
    # res.append(n.val)
    if n.right is not None:
        back_trace(n.right)
    # 后序
    # res.append(n.val)


if __name__ == '__main__':
    print('二叉树的遍历')
    # 构造二叉树
    a = Node('A')
    b = Node('B')
    c = Node('C')
    d = Node('D')
    e = Node('E')
    f = Node('F')
    g = Node('G')
    h = Node('H')
    i = Node('i')
    a.left = b
    a.right = c
    b.left = d
    b.right = e
    d.left = f
    d.right = g
    g.left = h
    g.right = i

    # 遍历二叉树
    back_trace(a)
    print(res)
